//给定三个字符串 s1, s2, s3, 验证 s3 是否是由 s1 和 s2 交错组成的。 
//
// 
//
// 示例 1： 
//
// 输入：s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac"
//输出：true
// 
//
// 示例 2： 
//
// 输入：s1 = "aabcc", s2 = "dbbca", s3 = "aadbbbaccc"
//输出：false 
// Related Topics 字符串 动态规划 
// 👍 334 👎 0

package leetcode.editor.cn;

//Java：交错字符串
public class P97InterleavingString {

    /**
     *
     * 思路： 动态规划。  一开始是想到了双指针+回溯想法，但是不会实现，就用了动态规划
     *      dp[m][n] 代表 m,n 可以构成 s3的 m+n 的长度
     *      dp[m][n] = (dp[m-1][n] 为true，且 s1 的m 的字符串与s3的相等) 或者 (dp[m][n-1] 为true，且 s2 的n 的字符串与s3的相等)
     *
     * 执行用时： 4 ms , 在所有 Java 提交中击败了 70.80% 的用户 内存消耗： 37.9 MB , 在所有 Java 提交中击败了 48.17% 的用户
     *
     */
    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public boolean isInterleave(String s1, String s2, String s3) {
            if (s3.length() != s1.length() + s2.length()) {
                return false;
            } else {
                if (s3.length() == 0) {
                    return true;
                }
            }

            int m = s1.length();
            int n = s2.length();

            // dp[m][n] 代表 m,n 可以构成 s3的 m+n 的长度
            // dp[3][5] 代表 s1的 aab 和 s2的 abbca 可以构成 s3[7]
            boolean[][] dp = new boolean[m + 1][n + 1];
            for (int i = 0; i < m; i++) {
                if (s1.charAt(i) == s3.charAt(i)) {
                    dp[i + 1][0] = true;
                } else {
                    break;
                }
            }
            for (int i = 0; i < n; i++) {
                if (s2.charAt(i) == s3.charAt(i)) {
                    dp[0][i + 1] = true;
                } else {
                    break;
                }
            }

            for (int j = 1; j <= s1.length(); j++) {
                for (int k = 1; k <= s2.length(); k++) {
                    int sNow = j + k - 1;   // s 当前下标
                    if (dp[j - 1][k]) {
                        dp[j][k] = s3.charAt(sNow) == s1.charAt(j - 1);
                    } else if (dp[j][k - 1]) {
                        dp[j][k] = s3.charAt(sNow) == s2.charAt(k - 1);
                    }
                }
            }

            return dp[m][n];
        }
    }
    //leetcode submit region end(Prohibit modification and deletion)

    public static void main(String[] args) {
        String s1 = "";
        String s2 = "";
        String s3 = "";
        Solution solution = new P97InterleavingString().new Solution();
        System.out.println(solution.isInterleave(s1, s2, s3));
        // TO TEST
    }

}